1. Field of the Invention
This invention relates to a method and apparatus for transforming, lighting and clipping tile data representing a polygon for purposes of displaying tile polygon on a computer graphics display system.
2. Description of the Related Art
a. General
Polygons are widely used in 3-D computer graphics, including computer aided design (CAD), molecular modeling, geometric solid modeling, and architecture. The performance of a computer graphics display may be improved through the ability to represent polygons accurately and efficiently.
A polygon is defined by a sequence of vertex data records, including vertex coordinates and other values such as vertex normal vectors, describing successive vertices of a closed boundary. These vertices are subject to several types of calculations, including transformations, lighting and clipping, before the final step of rasterization. Vertices are thus transformed from an original coordinate system in which the polygons are defined to a coordinate system in which the polygons are displayed or further processed; polygons are typically transformed several times in the course of the their overall processing. At an appropriate stage of transformation, the vertices are "lighted" by generating shading values from normal vector values and other data, as discussed below. At some stage of their processing, polygons are "clipped" to remove any polygon portions extending beyond defined clipping boundaries (generally planes that are orthogonal to the coordinate axes), generating new vertices and edges to replace any removed portions. Transformation, lighting and clipping are generally performed by a processor pipeline known as the transformation pipeline to speed the overall process. Polygons that have been transformed, lighted and clipped are finally rasterized by conversion to a pixel image that is stored in a frame buffer for display on a computer graphics display device.
Polygon clipping is central to this process, since the point at which it is performed in the transformation pipeline can greatly affect both the speed and accuracy of image rendering. Polygon clipping is discussed in such patents and other publications as Hodgman et al. U.S. Pat. No. 3,816,726; Barkans et al. U.S. Pat. No. 4,888,712; Piazza U.S. Pat. No. 4,958,305; Akeley et al. U.S. Pat. No. 5,051,737; Akeley et al., "High-Performance Polygon Rendering", Computer Graphics, Vol. 22, No. 4, pp. 239-246 (Aug. 1988); Foley et al., Computer Graphics: Principles and Practice, pp. 866-870 (2d ed. 1990); and Sutherland et al., "Reentrant Polygon Clipping", Communications of the ACM, Vol. 17, No. 1, pp. 32-42 (Jan. 1974), the disclosures of which are incorporated herein by reference. Transformation and lighting are discussed in the above-identified work of Foley et al., as well as in Gonzalez-Lopez et al. U.S. Pat. No. 4,866,637, the disclosure of which is likewise incorporated herein by reference.
Polygon vertex data may consist of simple vertex records, colored vertex records, or lightable vertex records. In the case of simple vertex records, each vertex is defined by its 2-D (x,y), 3-D (x,y,z), or 4-D homogeneous (wx,wy,wz,w) coordinates. The color of the resulting polygon is usually defined by a single constant color value which is shared by all points used to represent the shape of the polygon.
In the case of colored vertex records, the vertex data also includes a color value in addition to the coordinates found in the simple data records. Although it is possible to define colored vertex records for 2-D vertices, this is not very useful and is rarely encountered in practice. The vertex color values are most commonly derived from the results of illumination calculations on lightable vertex data records. The color values at points between these vertices are generally defined by some sort of interpolation between the vertex color values. Several types of color interpolation may be defined for the interior points of polygons. These methods are called shaded area fill methods or "Gouraud shading", and the resulting polygons are called "Gouraud-shaded polygons".
In the case of lightable vertex records, each vertex includes an explicit or implied reflectance normal vector in addition to the vertex coordinates of the simple vertex records. This type of vertex does not possess a color. Instead, each vertex has "material properties" such as ambient, diffuse, and specular reflection coefficients. In most cases, the same material properties are shared by all vertices and are not specified as part of the individual vertex records. The normal vectors, however, are typically specified independently for every vertex as a means of representing planar approximations to curved surfaces. The normal vectors, the material properties, and a set of light source definitions are used as parameters for lighting calculations which simulate the illumination of the polygon by one or more sources of light. The result of these lighting calculations is a color value equivalent to the color value contained within a colored vertex record.
Polygons may be rendered as hollow polygons, solid or "flat shaded" polygons, Gouraud-shaded polygons, or Phong-shaded polygons.
A hollow polygon is represented by straight lines connecting successive vertices, including a line joining the last vertex to the first vertex. Nothing is done in the interior of the polygon. Hollow polygons are rarely subject to lighting or shading, except for "depth cueing" (which requires no additional vertex data). Consequently, hollow polygons are typically defined using simple vertex records.
In the case of solid or "flat shaded" polygons, every point on the interior of a polygon is represented with a single constant color. This method is easily implemented on raster-based computer graphics display devices and is typically used for representing polygons defined by simple vertex records on raster-based displays.
A Gouraud-shaded polygon is divided into a set of pixels defined by a raster graphics display, and the color of each pixel is determined by interpolating between colors defined at the vertices. The colors at the vertices may be specified either directly through colored vertex records or evaluating lighting equations based on lightable vertex records. This becomes equivalent to the case of solid polygons for simple vertex records. The methods of interpolation are not unique, and several types of Gouraud-shaded area fill methods have been implemented based on various interpolation schemes. These methods generally produce equivalent results for triangles, but yield inconsistent results for polygons with four or more vertices.
A Phong-shaded polygon is divided into a set of pixels defined by a raster graphics display, and the color of each pixel is determined by evaluating lighting equations based on normal vectors and material properties interpolated between vertices. This method requires lightable vertex records, and produces more pleasing (realistic) colors than obtained by applying the Gouraud shading method to the same polygon. The resulting calculations, however, are much more costly than those in which lighting calculations are performed only at the vertices, and the speed of rendering (converting polygons to pixels) is much slower. Consequently, this approach is not generally used when interactive or real-time rendering or animation is required.
b. Clip Invariance
Prior art clipping methods such as that of Sutherland et al. (1974) were designed for the case of hollow polygons defined by simple vertex records. By the mid-1980s, however, the use of raster-based displays began to be extended to interactive 3-D computer graphics, with dedicated circuits for hidden surface removal (the z-buffer), geometry engines for transformations and clipping, and rasterizers capable of Gouraud-shaded area fills. At this point, it became necessary for the clipping logic to handle polygons with colored vertex records. The universally accepted solution to this problem seems to be based on a straightforward extension of the previous methods developed by Sutherland et al. In this case, if the vector joining two successive vertices must be clipped because it crosses some boundary, then the color at the point where the vector crosses this boundary is calculated by simple linear interpolation between the colors at each of the two original (unclipped) vertices. This produces the correct color at this point, but it disregards the consequences at the interior points within the remaining (clipped) portion of the polygon.
Prior art clipping methods do not address the problem of how to clip polygons with colored vertices because the polygons they were concerned with were defined by simple vertex records with hollow area fills. The practice of adding interpolated colors to vertices produced by such clipping methods, while a simple expedient, ignores the basic purpose of clipping, which is to remove the portions of a polygon which are considered invisible because they fall outside a certain region of space. A proper clipping method must preserve every property, including the color, of every pixel within the portion of the polygon which remains visible after clipping. This characteristic is called "clip invariance". Simply interpolating between vertex colors when clipping does not satisfy this requirement. Consequently, when a shaded polygon is clipped using conventional methods, the interior colors depend on how the polygon is clipped, as may be verified easily by drawing a shaded polygon and shifting it until part of it crosses a clipping boundary.